using System;
using System.Collections.Generic;
using System.Text;
using Eve.Data;

namespace Eve.Utility
{
    public class Autopilot
    {
        private class PathNode : IComparable<PathNode>
        {
            public PathNode Parent = null;
            public SolarSystem System;
            public double H;
            public double g = 0;
            public int jumps = 1;

            public double G
            {
                get
                {
                    double tg = g;
                    if (Parent != null) tg += Parent.G;
                    return tg;
                }
            }
            public double F { get { return G + H; } }
            public int Jumps
            {
                get
                {
                    if (jumps == 1 && Parent != null)
                        jumps += Parent.Jumps;
                    return jumps;
                }
            }

            public PathNode()
            {
            }
            public PathNode(PathNode parent, Eve.Data.SolarSystem system, double g, double h)
            {
                Parent = parent;
                System = system;
                this.g = g;
                H = h;
            }

            #region IComparable<PathNode> Members
            public int CompareTo(PathNode other)
            {
                return (int)(F - other.F);
            }
            #endregion
        }

        public static List<SolarSystem> GetShortestPath(EveData data, SolarSystem start, SolarSystem goal)
        {
            SortedList<double, PathNode> open = new SortedList<double, PathNode>();
            List<int> closed = new List<int>();

            PathNode startNode = new PathNode(null, start, 0, (goal.Location - start.Location).Length);
            open[startNode.F] = startNode;

            PathNode route = null;
            do
            {
                PathNode current = open[open.Keys[0]];
                open.Remove(open.Keys[0]);
                if (current.System.Id == goal.Id)
                {
                    route = current;
                    break;
                }

                closed.Add(current.System.Id);
                List<SolarSystem> jumps = current.System.Jumps;
                foreach (SolarSystem jump in jumps)
                {
                    if (closed.Contains(jump.Id)) continue;
                    double g = 0.0;
                    double h = (goal.Location - jump.Location).Length;
                    Vector fromLoc = current.System.Location;
                    Vector toLoc = jump.Location;
                    if (current.Parent != null)
                        fromLoc = current.Parent.System.Location;
                    g += 100000.0;  // prefer shorter
                    g += (toLoc - fromLoc).Length;
                    PathNode next = new PathNode(current, jump, g, h);
                    open.Add(next.F, next);
                }
            } while (open.Count > 0);
            if (route == null) return null;
            List<SolarSystem> ret = new List<SolarSystem>();
            while (route.Parent != null)
            {
                ret.Insert(0, route.System);
                route = route.Parent;
            }
            return ret;
        }
    }
}
